Singly Linked Lists

There are three types of Linked Lists used daily by Engineers, and the most popular of the lot is the Singly Linked Lists. Singly Linked Lists traverse in a single direction, and each node has the data and the pointer to the next node. In this article, let us understand the depths of Singly Linked Lists in the following order:

• What is Singly Linked List 
• Representation of a Singly Linked List
• Singly Linked List Operations
  • Traversing a Singly Linked List
  • Insertion an element in a Singly Linked List
  • Deletion on a Singly Linked List
  • Searching in a Singly Linked List
  • Sorting Singly Linked List
• Singly Linked List in C
• Singly Linked List in Python
• Singly Linked List Complexity

What is Singly Linked List 

Singly Linked Lists are the simplest of the lot, where every node contains some data and a pointer to the next node of the same data type. So, every node stores the address to the next node in the sequence.

Here, you have to remember that Singly Linked Lists only allow the traversal of data in a single direction.

Representation of Singly Linked Lists

A linked list is a chain of nodes, and each node has the following parts:

• Data Item
• Address to next node

Node is represented in the C programming language as follows:

struct node
{
  int d;
 struct node *n;
};

Node is represented in Python programming language as follows:

class node:
    def __init__(self, d):
        self.d = d
        self.n = None

Singly Linked List Operations

Traversal

Traversal refers to accessing elements in the list and displaying them as output. 

To traverse through the list, you have to keep moving the temp node to the next node until the temp is NULL. As soon as temp = NULL, it implies that you have reached the end of the list

//Travseral code in C

void DisplayList(struct node* node) {
  while (node != NULL) {
  printf(" %d ", node->d);
  node = node->n;
  }
}

//Traversal code in Python

 #Traverse the List
    def DisplayList(self):
        temp = self.head
        while (temp):
            print(temp.d)
            temp = temp.n

Insertion

There are three ways to insert an element in Singly Linked Lists.

Note: For all the types of insertion, you have to allocate memory and store data for a new node

• Insert at the beginning
  •  Change the next of new node to point to head
  •  Change the head to point to the newly created node

//Insertion code in C

void InserBeg(struct node** head_ref, int new_d) {
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
 
  node1->d = new_d;
  node1->n = (*head_ref);
  (*head_ref) = node1;
}

//Insertion code in Python

# Insert at the beginning
    def InserBeg(self, new_d):
        newnode = node(new_d)
 
        newnode.n = self.head
        self.head = newnode

• Insert at the midpoint/ after a node
  • Go to the node just before the required position of the new node
  • Change the next pointer to include a new node 

//Insertion code in C

// Insert a node after a node
void InserAf(struct node* p, int new_d) {
  if (p == NULL) {
  printf("Previous node must not be  NULL");
  return;
  }
 
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
  node1->d = new_d;
  node1->n = p->n;
  p->n = node1;
}

//Insertion code in Python

# Insert after a node
    def InserAf(self, p, new_d):
 
        if p is None:
            print("The node must be present in Linked List.")
            return
 
        newnode = node(new_d)
        newnode.n = p.n
        p.n = newnode

• Insert at the end
  • Go to the last node and change the next of the last node to the recently created node

//Insertion code in C

// Insert the the end
void InserEnd(struct node** head_ref, int new_d) {
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
  struct node* end = *head_ref; 
 
  node1->d = new_d;
  node1->n = NULL;
 
  if (*head_ref == NULL) {
  *head_ref = node1;
  return;
  }
 
  while (end->n != NULL) end = end->n;
 
  end->n = node1;
  return;
}

//Insertion code in Python

# Insert at the end
    def InserEnd(self, new_d):
        newnode = node(new_d)
 
        if self.head is None:
            self.head = newnode
            return
 
        end = self.head
        while (end.n):
            end = end.n
 
        end.n = newnode

Deletion

There are three ways to delete elements in Singly Linked Lists.

• To delete from the beginning, you have to point the head to the second element
• To delete after a node, you have to go to the element, before the one that has to be deleted and exclude the same by changing the next pointers.
• To delete from the end, you have to go to the second last element and change its next to NULL.

Here, since you have to traverse through the entire list to delete an element, you have to 

• Write the code to delete the node containing the key element which needs to be deleted.
• Include an if else loop for a case where the element to be deleted is not found in the List.

//Deletion in C

// Delete a node
void DelNode(struct node** head_ref, int key) {
  struct node *temp = *head_ref, *prev;
 
  if (temp != NULL && temp->d == key) {
  *head_ref = temp->n;
  free(temp);
  return;
  }
  while (temp != NULL && temp->d != key) {
  prev = temp;
  temp = temp->n;
  }
  if (temp == NULL) return;
  prev->n = temp->n;
 
  free(temp);
}

//Deletion code in Python

 # Deleting a node
    def DelNode(self, index):
 
        if self.head is None:
            return
 
        temp = self.head
 
        if index == 0:
            self.head = temp.n
            temp = None
            return
        for i in range(index - 1):
            temp = temp.n
            if temp is None:
                break
        if temp is None:
            return
 
        if temp.n is None:
            return
 
        n = temp.n.n
 
        temp.n = None
 
        temp.n = n

Searching

Let us consider you have to search for an “key” element in the Linked Lists. Now to find this item, you have to 

• Make HEAD as the current node and run the loop until the current node is NULL.
• In every iteration, you have to check if the value of the node = item. If YES, then return that item is found else continue the loop.

//Searching in C

// Search an element
int FindElement(struct node** head_ref, int key) {
  struct node* current = *head_ref;
 
  while (current != NULL) {
  if (current->d == key) return 1;
  current = current->n;
  }
  return 0;
}

//Searching in Python

# Search an element in Linked List
    def FindElement(self, key):
 
        current = self.head
 
        while current is not None:
            if current.d == key:
                return True
 
            current = current.n
 
        return False

Sorting

Let us consider that you wish to sort the elements in ascending order. Then follow the below steps to execute the same:

1. Make HEAD as current node
2. Create another node “newnode” for later use
3. If HEAD is NULL then return
4. Else execute the loop until you reach NULL
5. For every iteration, you have to 
6. Store the next node of current in “newnode”
7. Check if data of current node > next node. If YES, swap current node & newnode.

//Sorting in C

// Sort the linked list
void SortLL(struct node** head_ref) {
  struct node *current = *head_ref, *index = NULL;
  int temp;
 
  if (head_ref == NULL) {
  return;
  } else {
  while (current != NULL) {
    index = current->n;
 
    while (index != NULL) {
    if (current->d > index->d) {
      temp = current->d;
      current->d = index->d;
      index->d = temp;
    }
    index = index->n;
    }
    current = current->n;
  }
  }
}

//Sorting in Python

# Sort the linked list
    def SortLL(self, head):
        current = head
        index = node(None)
 
        if head is None:
            return
        else:
            while current is not None:
                # index points to the node n to current
                index = current.n
 
                while index is not None:
                    if current.d > index.d:
                        current.d, index.d = index.d, current.d
 
                    index = index.n
                current = current.n

Singly Linked Lists in C

Refer to the following code to understand how to create a Singly Linked Lists and perform various operations in C.

#include <stdio.h>
#include <stdlib.h>
 
// Create a node
struct node {
  int d;
  struct node* n;
};
 
// Traverse the linked list
void DisplayList(struct node* node) {
  while (node != NULL) {
  printf(" %d ", node->d);
  node = node->n;
  }
}
 
// Insert at the beginning
void InserBeg(struct node** head_ref, int new_d) {
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
 
  node1->d = new_d;
  node1->n = (*head_ref);
  (*head_ref) = node1;
}
 
// Insert a node after a node
void InserAf(struct node* p, int new_d) {
  if (p == NULL) {
  printf("Previous node must not be NULL");
  return;
  }
 
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
  node1->d = new_d;
  node1->n = p->n;
  p->n = node1;
}
 
// Insert the the end
void InserEnd(struct node** head_ref, int new_d) {
  struct node* node1 = (struct node*)malloc(sizeof(struct node));
  struct node* end = *head_ref; 
 
  node1->d = new_d;
  node1->n = NULL;
 
  if (*head_ref == NULL) {
  *head_ref = node1;
  return;
  }
 
  while (end->n != NULL) end = end->n;
 
  end->n = node1;
  return;
}
 
// Delete a node
void DelNode(struct node** head_ref, int key) {
  struct node *temp = *head_ref, *prev;
 
  if (temp != NULL && temp->d == key) {
  *head_ref = temp->n;
  free(temp);
  return;
  }
  while (temp != NULL && temp->d != key) {
  prev = temp;
  temp = temp->n;
  }
 
  if (temp == NULL) return;
  prev->n = temp->n;
 
  free(temp);
}
 
// Search an element
int FindElement(struct node** head_ref, int key) {
  struct node* current = *head_ref;
 
  while (current != NULL) {
  if (current->d == key) return 1;
  current = current->n;
  }
  return 0;
}
 
// Sort the linked list
void SortLL(struct node** head_ref) {
  struct node *current = *head_ref, *index = NULL;
  int temp;
 
  if (head_ref == NULL) {
  return;
  } else {
  while (current != NULL) {
    index = current->n;
 
    while (index != NULL) {
    if (current->d > index->d) {
      temp = current->d;
      current->d = index->d;
      index->d = temp;
    }
    index = index->n;
    }
    current = current->n;
  }
  }
}
 
int main() {
  struct node* head = NULL;
 
  InserBeg(&head, 31);
  InserEnd(&head, 19);
  InserBeg(&head, 62);
  InserEnd(&head, 12);
  InserEnd(&head, 85);
  InserAf(head->n, 10);
 
  printf("Linked List after inserting elements :
");
  DisplayList(head);
 
  printf("
");
 
  int item = 85;
  if (FindElement(&head, item)) {
  printf("
The element %d is found", item);
  } else {
  printf("
The element %d is not found", item);
  }
  printf("
");
 
  printf("
Linked List after deleting element at node 4 : 
");
  DelNode(&head, 12);
  DisplayList(head);
 
 
  SortLL(&head);
  printf("
");  
  printf("
Linked List after sorting in ascending order : 
");
  DisplayList(head);
}

Output:

Singly Linked List in Python

Refer to the following code to understand how to create a Singly Linked Lists and perform various operations in Python.

# Create a node
class node:
    def __init__(self, d):
        self.d = d
        self.n = None
 
#Define class LinkedList
class LinkedList:
 
    def __init__(self):
        self.head = None
 
    #Traverse the List
    def DisplayList(self):
        temp = self.head
        while (temp):
            print(temp.d)
            temp = temp.n
 
    # Insert at the beginning
    def InserBeg(self, new_d):
        newnode = node(new_d)
 
        newnode.n = self.head
        self.head = newnode
 
    # Insert after a node
    def InserAf(self, p, new_d):
 
        if p is None:
            print("The given p node must in LinkedList.")
            return
 
        newnode = node(new_d)
        newnode.n = p.n
        p.n = newnode
 
    # Insert at the end
    def InserEnd(self, new_d):
        newnode = node(new_d)
 
        if self.head is None:
            self.head = newnode
            return
 
        end = self.head
        while (end.n):
            end = end.n
 
        end.n = newnode
 
    # Deleting a node
    def DelNode(self, index):
 
        if self.head is None:
            return
 
        temp = self.head
 
        if index == 0:
            self.head = temp.n
            temp = None
            return
        for i in range(index - 1):
            temp = temp.n
            if temp is None:
                break
        if temp is None:
            return
 
        if temp.n is None:
            return
 
        n = temp.n.n
 
        temp.n = None
 
        temp.n = n
 
    # Search an element in Linked List
    def FindElement(self, key):
 
        current = self.head
 
        while current is not None:
            if current.d == key:
                return True
 
            current = current.n
 
        return False
 
    # Sort the linked list
    def SortLL(self, head):
        current = head
        index = node(None)
 
        if head is None:
            return
        else:
            while current is not None:
                # index points to the node n to current
                index = current.n
 
                while index is not None:
                    if current.d > index.d:
                        current.d, index.d = index.d, current.d
 
                    index = index.n
                current = current.n
 
 
if __name__ == '__main__':
#Start the Linked List as empty elements
    llist = LinkedList()
    #Insert elements
    llist.InserBeg(31)
    llist.InserEnd(19)
    llist.InserBeg(62)
    llist.InserEnd(12)
    llist.InserEnd(85)
    llist.InserAf(llist.head.n, 10)
 
    print('Linked List after inserting elements :')
    llist.DisplayList()
 
     #Search for elements
    print()
    item = 85
    if llist.FindElement(item):
        print("
The element " + str(item) + " is found")
    else:
        print("
The element " + str(item) + " is not found ")
 
    #Delete elements
    print("
Linked List after deleting element at node '4'")
    llist.DelNode(4)
    llist.DisplayList()
 
    #sort in ascending order
    llist.SortLL(llist.head)
    print("
Linked List after sorting in ascending order : ")
    llist.DisplayList()

Output:

Singly Linked List Complexity

Time Complexity

	Average Scenario	Worst Scenario
Search	O(n)	O(n)
Insertion	O(1)	O(1)
Deletion	O(1)	O(1)

Space Complexity of Linked List is O(n).

With this, we end this article on Singly Linked List and how to implement it. We hope you found it informative. 

Top Trending Tech Articles:
Career Opportunities after BTech Online Python Compiler What is Coding Queue Data Structure Top Programming Language Trending DevOps Tools Highest Paid IT Jobs Most In Demand IT Skills Networking Interview Questions Features of Java Basic Linux Commands Amazon Interview Questions

Recently completed any professional course/certification from the market? Tell us what liked or disliked in the course for more curated content.

Click here to submit its review with Shiksha Online.